一个快排有关的问题

问题来源于我的邀请赛里面的这道题。

此题std

本来是一个很正常的贪心，然后神Sooke提出了一个结论，我整理后如下：

设$f(n)$是这个题输出的数组中，满足$a[i]=i$的一段前缀的长度，那么

$f(2)=2$

$f(2^n)=1,n>1$

$f(n)=\frac{\text{n的最大奇因子}-1}{2},otherwise$

不太严谨的口胡证明

首先$n\le4$可以直接验证得到，对于$n>4$：

分析那个标程，可以发现$f(n)$就是注释标出的那行执行到的次数

如果某一时刻$b$数组的$[l,r)$区间中最小值在$b[l]$的位置，那么这就是一个好的状态

对于一个好的状态，如果$r-l$是奇数，$2$轮就能回到好的状态，并且这个过程中执行了一次注释标出的那行，于是

$f(n)=f(n-2)+1,\text{n是奇数}$

如果$r-l$是偶数，$\frac{r-l}{2}$轮才能回到好的状态，这个过程中没有执行到注释标出的那行

$f(n)=f(\frac{n}{2}),\text{n是偶数}$

结合$n\le4$的边界条件就可以推出来了